/**
 * 面试题 04.06. 后继者
 * https://leetcode-cn.com/problems/successor-lcci/
 */
public class Solutions_mianshi_04_06 {
    public static void main(String[] args) {
//        TreeNode root = new TreeNode(2);
//        root.left = new TreeNode(1);
//        root.right = new TreeNode(3);
//        TreeNode p = new TreeNode(1);  // output: 2

        TreeNode root = new TreeNode(5);
        root.left = new TreeNode(3);
        root.left.left = new TreeNode(2);
        root.left.right = new TreeNode(4);
        root.left.left.left = new TreeNode(1);
        root.right = new TreeNode(6);
//        TreeNode p = new TreeNode(6);  // output: null
//        TreeNode p = new TreeNode(4);  // output: 5
        TreeNode p = new TreeNode(2);  // output: 3

        TreeNode result = inorderSuccessor(root, p);
        System.out.println(result);
    }

    private static TreeNode preNode = null;
    /**
     * 解法一：递归-中序遍历 root，记录下前一节点，若遍历某一节点时，前一节点等于 p，那么 p 的后继结点就是当前节点
     */
    public static TreeNode inorderSuccessor(TreeNode root, TreeNode p) {
        if (root == null || p == null) {
            return null;
        }
        TreeNode leftRes = inorderSuccessor(root.left, p);
        if (leftRes != null) {
            // 提前返回
            return leftRes;
        }
        // 找到 p 的后继节点
        if (preNode != null && preNode.val == p.val) {
            return root;
        }
        preNode = root;
        TreeNode rightRes = inorderSuccessor(root.right, p);
        return rightRes;
    }
}
